
// greedy

#include <stdio.h>
#include <stdlib.h>

FILE *fp;

int N;
int C;
int *w;      // array of item weights
int *v;      // array of item values (or profits)
int *kindex;  // array of indexes to the items
int QUIET=0; // can be set to 1 to suppress output

extern void read_knapsack_instance(char *filename);
extern void print_instance();
extern void sort_by_ratio();
extern int print_sol2(int *s, int *tv, int *tw);
void greedy();

int main(int argc, char *argv[])
{
  read_knapsack_instance(argv[1]);
  print_instance();
  greedy();
  return(0);
}

void greedy()
{
  int tw=0; // current total weight of the items in the knapsack
  int tv=0; //  current total profit of the items in the knapsack
  int i=1;
  int x[N+1];

  sort_by_ratio(); // sort by profit-to-weight ratio

  // take every item in descending profit-to-weight ratio order and if it fits, add it to the knapsack


  /* ADD CODE HERE TO COMPUTE THE GREEDY SOLUTION */
  for (i=1;i<= N; i++)
  {
    x[i]=0;
    if(tw +w[kindex[i]] <= C)
    {
      tw+=w[kindex[i]];
      tv+=v[kindex[i]];
      x[i]=1; 
    }
  }
    
  
  printf("The greedy solution - not necessarily optimal - is:\n");
  print_sol2(x, &tv, &tw);  
}

